/**
 * Universidad Del Valle De Guatemala.
 * Algoritmos y Estructuras de Datos.
 * Sección 20.
 * Miguel Enrique Zea Arenales.
 * Carné 09238.
 * Hoja de Trabajo 8.
 * 08/11/2012
 */
package shortestpath;

import java.util.ArrayList;

/**
 *
 * @author Miguel Zea
 */
public class ShortestPath {
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        ArrayList<Integer> t = new ArrayList<>();
        DirectedGraphMatrix test = new DirectedGraphMatrix(3);
        test.addVertex("A");
        test.addVertex("B");
        test.addVertex("C");
        test.addEdge("A", "B", 8);
        test.addEdge("A", "C", 5);
        test.addEdge("B", "A", 3);
        test.addEdge("C", "B", 2);
        
        int[][] temp, temp2;
        temp = test.getAdjMat();
        temp2 = initPathMatrix(temp);
        
        for(int i = 0; i < test.size(); i++) {
            System.out.print("|");
            System.out.print("\t");
            for(int j = 0; j < test.size(); j++) {
                System.out.print(temp[i][j]);
                System.out.print("\t");
            }
            System.out.print("\t");
            System.out.println("|");
        }
        
        t = PathSearcher.FloydPathSearch(temp, temp2, 0, 1);
        
        //------------------
        System.out.println();
        for(int i = 0; i < test.size(); i++) {
            System.out.print("|");
            System.out.print("\t");
            for(int j = 0; j < test.size(); j++) {
                System.out.print(temp[i][j]);
                System.out.print("\t");
            }
            System.out.print("\t");
            System.out.println("|");
        }
        //-----------------
        
        //-----------------
        System.out.println();
        for(int i = 0; i < test.size(); i++) {
            System.out.print("|");
            System.out.print("\t");
            for(int j = 0; j < test.size(); j++) {
                System.out.print(temp2[i][j]);
                System.out.print("\t");
            }
            System.out.print("\t");
            System.out.println("|");
        }
        //-----------------
        
        //System.out.println(t.toString());
        
        System.out.print(test.getVertex(t.get(0)).toString() + " ");
        for(int i = 1; i < t.size() - 1; i++) {
            System.out.print("-> " + test.getVertex(t.get(i)).toString() + " ");
        }
        System.out.println();
        System.out.println("Peso: " + t.get(t.size()-1).toString());
        System.out.println(test.getVertex(PathSearcher.GraphCenter(temp)));
    }
    
    public static int[][] initPathMatrix(int[][] adjMatrix) {
        int i, j, n;
        n = adjMatrix.length;
        int[][] path = new int[n][n];
        
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                if(adjMatrix[i][j] == 999999) {
                    path[i][j] = -1;
                } else {
                    path[i][j] = i;
                }
            }
        }
        
        for(i = 0; i < n; i++) {
            path[i][i] = i;
        }
        return path;
    }
}
